/*
 * Copyright (c) Huawei Technologies Co., Ltd. 2022-2022. All rights reserved.
 */

/**
 * 堆工具类
 * 根据传入的比较函数确定元素的优先级
 * 支持push/pop/update/clear/peek/empty操作
 *
 * @since 2022/9/17
 */
export class Heap<T> {
  private elements: T[] = [];
  private element2index: Map<T, number> = new Map<T, number>();
  private size = 0;
  private readonly compare: (a: T, b: T) => number;

  constructor(compare: (a: T, b: T) => number) {
    this.compare = compare;
  }

  update(x: T): void {
    if (!this.element2index.has(x)) {
      return;
    }
    this.up(this.element2index.get(x)!);
    this.down(this.element2index.get(x)!);
  }

  clear(): void {
    this.size = 0;
  }

  peek(): T | undefined {
    if (this.size === 0) {
      return undefined;
    }
    return this.elements[1];
  }

  push(x: T): void {
    this.size++;
    this.elements[this.size] = x;
    this.element2index.set(x, this.size);
    this.up(this.size);
  }

  pop(): T | undefined {
    if (this.size === 0) {
      return undefined;
    }
    this.swap(1, this.size);
    this.size--;
    this.down(1);
    this.element2index.delete(this.elements[this.size + 1]);
    return this.elements[this.size + 1];
  }

  empty(): boolean {
    return this.size === 0;
  }

  private up(u: number): void {
    let q = Math.ceil(u / 2);
    while (q >= 1 && this.compare(this.elements[u]!, this.elements[q]!) < 0) {
      this.swap(u, q);
      u = q;
      q = Math.ceil(u / 2);
    }
  }

  private down(u: number): void {
    let t: number = u;
    if (u * 2 <= this.size && this.compare(this.elements[u * 2]!, this.elements[t]!) < 0) t = u * 2;
    if (u * 2 + 1 <= this.size && this.compare(this.elements[u * 2 + 1]!, this.elements[t]!) < 0) t = u * 2 + 1;
    if (u !== t) {
      this.swap(u, t);
      this.down(t);
    }
  }

  private swap(a: number, b: number): void {
    const temp = this.elements[a];
    this.elements[a] = this.elements[b]!;
    this.elements[b] = temp!;
    this.element2index.set(this.elements[a], a);
    this.element2index.set(this.elements[b], b);
  }
}
